#include<iostream>
using namespace std;
typedef long long LL;


LL qmi(LL a,LL k,LL p){
    LL ans=1;
    while(k){
        if(k&1)ans=ans*a%p;
        k>>=1;
        a=a*a%p;
    }
    return ans;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        LL a,p;
        cin>>a>>p;
        if(a%p==0)cout<<"impossible";
        else cout<<qmi(a,p-2,p);
        cout<<endl;
    }
    
    
    return 0;
}
